# 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 
# 
#  有效 二叉搜索树定义如下： 
# 
#  
#  节点的左子树只包含 小于 当前节点的数。 
#  节点的右子树只包含 大于 当前节点的数。 
#  所有左子树和右子树自身必须也是二叉搜索树。 
#  
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：root = [2,1,3]
# 输出：true
#  
# 
#  示例 2： 
# 
#  
# 输入：root = [5,1,4,null,null,3,6]
# 输出：false
# 解释：根节点的值是 5 ，但是右子节点的值是 4 。
#  
# 
#  
# 
#  提示： 
# 
#  
#  树中节点数目范围在[1, 104] 内 
#  -231 <= Node.val <= 231 - 1 
#  
#  Related Topics 树 深度优先搜索 二叉搜索树 二叉树 
#  👍 1254 👎 0


from typing import List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        stack = []
        val = float('-inf')
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if root.val <= val:
                return False
            root = root.right
        return True


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 迭代中序遍历
def inorder(r: TreeNode):
    ans = []
    stack = []
    while stack or r:
        while r:
            stack.append(r)
            r = r.left
        node = stack.pop()
        ans.append(node.val)
        r = node.right
    return ans


# 1: 递归
# node 是否在(l, r) 之间, 如果是递归左右子树
# 左子树 (l, node), 右子树(node, r)
#     def isValidBST(self, root: TreeNode) -> bool:
#         def valid_node(node: TreeNode, low=float('-inf'), high=float('inf')) -> bool:
#             # 空节点是二叉搜索树
#             if not node:
#                 return True
#
#             if node.val <= low or node.val >= high:
#                 return False
#
#             if not valid_node(node.left, low, node.val):
#                 return False
#             if not valid_node(node.right, node.val, high):
#                 return False
#             return True
#
#         return valid_node(root)

# 2: 中序遍历, 递增
#     def isValidBST(self, root: TreeNode) -> bool:
#         stack, inorder = [], float('-inf')
#         while stack or root:
#             while root:
#                 stack.append(root)
#                 root = root.left
#             root = stack.pop()
#             # 递增
#             if root.val <= inorder:
#                 return False
#             inorder = root.val
#             root = root.right
#
#         return True

if __name__ == '__main__':
    s = Solution()
    # [2, 1, 3]
    t1 = TreeNode(2, TreeNode(1), TreeNode(3))
    r1 = s.isValidBST(t1)
    assert r1, r1
